package top.minuy.structure.graph.representations.table;

import java.io.File;
import java.io.IOException;
import java.util.*;

/**
 * 带权图
 * 正式在后面的例子中使用的图的表示类 简单图
 * 使用基于红黑树的邻接表实现
 * V0.2
 * 带方向
 * V0.3动态的增加，删除边，增加，删除点，使用字符串作为顶点名称标记
 *
 * @author Minuy
 * @time 0:15
 * @date 2021/11/27
 */
public class WeightedGraphDynamic implements Cloneable {
    private int V; // 顶点个数
    private int E; // 边的条数
    private Map<String, Map<String, Integer>> adj; // 邻接表，（顶点名，邻接表（邻边顶点名，权值））
    private boolean isDirected; // 是否有向

    /**
     * 构造函数，构造一个有权图
     *
     * @param fileName 加载的文件名
     * @author Minuy
     * @date 2021/11/15 22:29
     */
    public WeightedGraphDynamic(String fileName) {
        this(fileName, false);
    }

    /**
     * 创建一个空无向有权图
     *
     * @author Minuy
     * @date 2021/11/28 16:50
     */
    public WeightedGraphDynamic() {
        this(null, false);
    }

    /**
     * 创建一个有权图
     *
     * @param isDirected 指定是否有向
     * @author Minuy
     * @date 2021/11/28 16:50
     */
    public WeightedGraphDynamic(boolean isDirected) {
        this(null, isDirected);
    }

    /**
     * 构造函数，从文件构造一个有权图
     *
     * @param fileName   加载的文件名
     * @param isDirected 指定是否有向
     * @author Minuy
     * @date 2021/11/28 16:51
     */
    public WeightedGraphDynamic(String fileName, boolean isDirected) {

        // 创建邻接表
        adj = new HashMap<>();

        this.isDirected = isDirected;

        if (fileName == null) {
            return;
        }

        File file = new File(fileName);

        // 这种语法可以不用手动关闭输入流
        try (Scanner scanner = new Scanner(file)) {
            int v = scanner.nextInt(); // 读入顶点数量
            if (0 > v) {
                // 顶点数量 必须是非负数的
                throw new IllegalArgumentException("V must be non-negative.");
            }

            // 添加顶点
            for (int i = 0; i < v; i++) {
                addVertex(i);
            }

            int e = scanner.nextInt(); // 读入边的数量
            if (0 > e) {
                // 边数量 必须是非负数的
                throw new IllegalArgumentException("E must be non-negative.");
            }
            for (int i = 0; i < e; i++) {
                int a = scanner.nextInt(); // 读入第一个顶点
                validateVertex(a);
                int b = scanner.nextInt(); // 读入第二个顶点
                validateVertex(b);
                int weight = scanner.nextInt(); // 读入权值

                addEdge(a, b, weight);
            }
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    /**
     * 添加一个顶点到图中
     *
     * @param v 要添加顶点的ID
     * @author Minuy
     * @date 2021/11/28 9:27
     */
    public void addVertex(int v) {
        addVertex(String.valueOf(v));
    }

    /**
     * 添加一个顶点到图中
     *
     * @param v 要添加顶点的名字
     * @author Minuy
     * @date 2021/11/28 9:28
     */
    public void addVertex(String v) {
        adj.put(v, new HashMap<>());
        V++;
    }

    /**
     * 删除一个点
     * 返回值：
     * Map：out中是有向图被删除顶点的出边
     * Map：in中是有向图被删除顶点的入边
     * Map：edge中是无向图被删除顶点的邻边
     *
     * @param v 顶点id
     * @return Map<String, Map < String, Integer>> 被删除的顶点的出边和进边
     * @author Minuy
     * @date 2021/11/28 10:20
     */
    public Map<String, Map<String, Integer>> removeVertex(int v) {
        return removeVertex(String.valueOf(v));
    }

    /**
     * 删除一个点
     * 返回值：
     * Map：out中是有向图被删除顶点的出边
     * Map：in中是有向图被删除顶点的入边
     * Map：edge中是无向图被删除顶点的邻边
     *
     * @param v 顶点名
     * @return Map<String, Map < String, Integer>> 被删除的顶点的出边和进边
     * @author Minuy
     * @date 2021/11/28 10:20
     */
    public Map<String, Map<String, Integer>> removeVertex(String v) {
        validateVertex(v);
        Map<String, Map<String, Integer>> ret = new HashMap<>();
        Map<String, Integer> removeOut = adj.remove(v);
        if (isDirected()) {
            // 被删除点的出边
            E-=removeOut.size();

            // 被删除点的进边
            Map<String, Integer> removeIn = new HashMap<>();

            // 待删除信息
            Set<String> removeEdge = new HashSet<>();

            // 找进边
            for (Map.Entry<String, Map<String, Integer>> w : adj.entrySet()) {
                // V : 每一个顶点，《顶点名，邻接表》
                for (Map.Entry<String, Integer> vTable : w.getValue().entrySet()) {
                    // vTable：每一个邻边关系《相邻顶点名，权》
                    if (vTable.getKey().equals(v)) {
                        removeEdge.add(w.getKey());
                        Integer weighted = adj.get(w.getKey()).get(vTable.getKey());
                        removeIn.put(w.getKey(), weighted);
                    }
                }
            }

            // 为了避免并发修改异常，先把要删除的存储下来，然后再一一删除
            for (String w : removeEdge) {
                adj.get(w).remove(v);
                E--;
            }

                ret.put("out", removeOut);
                ret.put("in", removeIn);
        }else {
            // 为了避免并发修改异常，先把要删除的存储下来，然后再一一删除
            for (String w : removeOut.keySet()) {
                adj.get(w).remove(v);
                E--;
            }
            ret.put("edge", removeOut);
        }
        V--;
        return ret;
    }


    /**
     * 添加一条边
     *
     * @param v      开始顶点
     * @param w      结束顶点
     * @param weight 权
     * @author Minuy
     * @date 2021/11/28 10:31
     */
    public void addEdge(int v, int w, int weight) {
        addEdge(String.valueOf(v), String.valueOf(w), weight);
    }

    /**
     * 添加一条边
     *
     * @param v      开始顶点
     * @param w      结束顶点
     * @param weight 权
     * @author Minuy
     * @date 2021/11/28 16:49
     */
    public void addEdge(int v, String w, int weight) {
        addEdge(String.valueOf(v), w, weight);
    }

    /**
     * 添加一条边
     *
     * @param v      开始顶点
     * @param w      结束顶点
     * @param weight 权
     * @author Minuy
     * @date 2021/11/28 16:50
     */
    public void addEdge(String v, int w, int weight) {
        addEdge(v, String.valueOf(w), weight);
    }

    /**
     * 添加一条边
     *
     * @param v      开始顶点
     * @param w      结束顶点
     * @param weight 权
     * @author Minuy
     * @date 2021/11/28 10:32
     */
    public void addEdge(String v, String w, int weight) {
        validateVertex(v);
        validateVertex(w);

        if (v.equals(w)) {
            // 自环，不允许出现在简单图中
            throw new IllegalArgumentException("Self Loop is Detected!");
        }

        if (adj.get(v).containsKey(w)) {
            // 平行边，不允许出现在简单图中
            // 若其他地方需要用到平行边，一般我们保留最小的那个平行边的权值，
            // 也可当做没有平行边来处理
            throw new IllegalArgumentException("Parallel Edges are Detected!");
        }

        adj.get(v).put(w, weight); // 连接两个顶点
        if (!isDirected()) {// 有向图维护度
            adj.get(w).put(v, weight); // 无向图的表示是两边都相连的
        }

        // 维护E
        E++;
    }


    /**
     * 删除一条边
     *
     * @param v 顶点1
     * @param w 顶点2
     * @return int 边的度
     * @author Minuy
     * @date 2021/11/28 10:28
     */
    public int removeEdge(String v, String w) {
        validateVertex(v);
        validateVertex(w);

        int weighted = getWeight(v, w);

        if (adj.get(v).containsKey(w)) {
            E--;

            adj.get(v).remove(w); // 删除边，不存在不会报错

            if (!isDirected()) { // 如果无向才删除“平行边”
                adj.get(w).remove(v);
            }
        }

        return weighted;
    }

    /**
     * 删除一条边
     *
     * @param v 顶点1
     * @param w 顶点2
     * @return int 边的度
     * @author Minuy
     * @date 2021/11/24 21:58
     */
    public int removeEdge(int v, int w) {
        return removeEdge(String.valueOf(v), String.valueOf(w));
    }

    /**
     * 删除一条边
     *
     * @param v 顶点1
     * @param w 顶点2
     * @return int 边的度
     * @author Minuy
     * @date 2021/11/28 16:49
     */
    public int removeEdge(int v, String w) {
        return removeEdge(String.valueOf(v), w);
    }

    /*** 删除一条边
     *
     * @param v 顶点1
     * @param w 顶点2
     * @return int 边的度
     * @author Minuy
     * @date 2021/11/28 16:49
     */
    public int removeEdge(String v, int w) {
        return removeEdge(v, String.valueOf(w));
    }

    /**
     * 验证顶点序号的合法性
     *
     * @param v 顶点值
     * @author Minuy
     * @date 2021/11/15 17:26
     */
    public void validateVertex(int v) {
        validateVertex(String.valueOf(v));
    }

    /**
     * 验证顶点序号的合法性
     *
     * @param v 顶点值
     * @author Minuy
     * @date 2021/11/28 10:26
     */
    public void validateVertex(String v) {
        if (!adj.containsKey(v)) {
            throw new IllegalArgumentException("The graph not has vertex " + v + ".");
        }
    }

    /**
     * 只读，边的数量
     *
     * @return int 边的数量
     * @author Minuy
     * @date 2021/11/15 17:35
     */
    public int E() {
        return E;
    }

    /**
     * 只读，顶点的数量
     *
     * @return int 顶点的数量
     * @author Minuy
     * @date 2021/11/15 17:35
     */
    public int V() {
        return V;
    }

    /**
     * 验证两个顶点之间是否有变
     *
     * @param v 顶点1的序号
     * @param w 顶点2的序号
     * @return boolean 有无边
     * @author Minuy
     * @date 2021/11/28 10:26
     */
    public boolean hasEdge(String v, String w) {
        validateVertex(v);
        validateVertex(w);
        return adj.get(v).containsKey(w);
    }

    /**
     * 验证两个顶点之间是否有变
     *
     * @param v 顶点1的序号
     * @param w 顶点2的序号
     * @return boolean 有无边
     * @author Minuy
     * @date 2021/11/15 17:38
     */
    public boolean hasEdge(int v, int w) {
        return hasEdge(String.valueOf(v), String.valueOf(w));
    }

    /**
     * 验证两个顶点之间是否有变
     *
     * @param v 顶点1的序号
     * @param w 顶点2的序号
     * @return boolean 有无边
     * @author Minuy
     * @date 2021/11/28 16:35
     */
    public boolean hasEdge(String v, int w) {
        return hasEdge(v, String.valueOf(w));
    }

    /**
     * 验证两个顶点之间是否有变
     *
     * @param v 顶点1的序号
     * @param w 顶点2的序号
     * @return boolean 有无边
     * @author Minuy
     * @date 2021/11/28 16:36
     */
    public boolean hasEdge(int v, String w) {
        return hasEdge(String.valueOf(v), w);
    }

    /**
     * 返回与顶点v相邻的所有顶点
     *
     * @param v 顶点v
     * @return Iterable<String> 与顶点v相邻的所有顶点
     * @author Minuy
     * @date 2021/11/15 19:55
     */
    public Iterable<String> adj(int v) {
        return adj(String.valueOf(v));
    }

    /**
     * 返回顶点v的邻接顶点
     *
     * @param v 顶点v
     * @return Iterable<String> 顶点v的邻接顶点
     * @author Minuy
     * @date 2021/11/28 16:29
     */
    public Iterable<String> adj(String v) {
        validateVertex(v);
        return adj.get(v).keySet();
    }

    /**
     * 重新设置边的权值
     *
     * @param v      顶点v，边的起点
     * @param w      顶点v，边的终点
     * @param weight 新的权值
     * @author Minuy
     * @date 2021/11/28 16:58
     */
    public void setWeight(int v, int w, int weight) {
        setWeight(String.valueOf(v), String.valueOf(w), weight);
    }

    /**
     * 重新设置边的权值
     *
     * @param v      顶点v，边的起点
     * @param w      顶点v，边的终点
     * @param weight 新的权值
     * @author Minuy
     * @date 2021/11/28 16:58
     */
    public void setWeight(String v, int w, int weight) {
        setWeight(v, String.valueOf(w), weight);
    }

    /**
     * 重新设置边的权值
     *
     * @param v      顶点v，边的起点
     * @param w      顶点v，边的终点
     * @param weight 新的权值
     * @author Minuy
     * @date 2021/11/28 16:58
     */
    public void setWeight(int v, String w, int weight) {
        setWeight(String.valueOf(v), w, weight);
    }

    /**
     * 重新设置边的权值
     *
     * @param v      顶点v，边的起点
     * @param w      顶点v，边的终点
     * @param weight 新的权值
     * @author Minuy
     * @date 2021/11/28 16:57
     */
    public void setWeight(String v, String w, int weight) {
        hasEdge(v, w);
        adj.get(v).put(w, weight);
        if (!isDirected()) {
            adj.get(w).put(v, weight);
        }
    }

    /**
     * 获取一条边的权值
     *
     * @param v 边的一端顶点
     * @param w 边的另一端顶点
     * @return int 这条边的权值
     * @author Minuy
     * @date 2021/11/25 9:31
     */
    public int getWeight(int v, int w) {
        return getWeight(String.valueOf(v), String.valueOf(w));
    }

    /**
     * 获取一条边的权值
     *
     * @param v 边的一端顶点
     * @param w 边的另一端顶点
     * @return int 这条边的权值
     * @author Minuy
     * @date 2021/11/28 16:59
     */
    public int getWeight(String v, int w) {
        return getWeight(v, String.valueOf(w));
    }

    /**
     * 获取一条边的权值
     *
     * @param v 边的一端顶点
     * @param w 边的另一端顶点
     * @return int 这条边的权值
     * @author Minuy
     * @date 2021/11/28 16:59
     */
    public int getWeight(int v, String w) {
        return getWeight(String.valueOf(v), w);
    }

    /**
     * 获取一条边的权值
     *
     * @param v 边的一端顶点
     * @param w 边的另一端顶点
     * @return int 这条边的权值
     * @author Minuy
     * @date 2021/11/28 10:30
     */
    public int getWeight(String v, String w) {
        if (hasEdge(v, w)) {
            return adj.get(v).get(w);
        }
        throw new IllegalArgumentException(String.format("Not has edge %s-%s.", v, w));
    }

    /**
     * 获取顶点v的度
     *
     * @param v 顶点v
     * @return int 顶点v的度
     * @author Minuy
     * @date 2021/11/15 17:46
     */
    public int degree(int v) {
        return degree(String.valueOf(v));
    }

    /**
     * 获取顶点v的度
     *
     * @param v 顶点v
     * @return int 顶点v的度
     * @author Minuy
     * @date 2021/11/28 10:47
     */
    public int degree(String v) {
        if (isDirected()) {
            throw new RuntimeException("The degree only works in directed graph.");
        }
        validateVertex(v);
        return adj.get(v).size();
    }


    /**
     * 入度
     *
     * @param v 顶点v
     * @return int 入度
     * @author Minuy
     * @date 2021/11/27 10:05
     */
    public int indegree(int v) {
        return indegree(String.valueOf(v));
    }

    /**
     * 入度
     *
     * @param v 顶点v
     * @return int 入度
     * @author Minuy
     * @date 2021/11/28 10:48
     */
    public int indegree(String v) {
        if (!isDirected()) {
            throw new RuntimeException("The indegree only works in directed graph.");
        }

        validateVertex(v);

        int ind = 0;
        for (int w = 0; w < V(); w++) {
            for (String x : adj(w)) {
                if (x.equals(v)) {
                    ind++;
                }
            }
        }
        return ind;
    }

    /**
     * 出度
     *
     * @param v 顶点v
     * @return int 出度
     * @author Minuy
     * @date 2021/11/27 10:05
     */
    public int outdegree(int v) {
        return outdegree(String.valueOf(v));
    }

    /**
     * 出度
     *
     * @param v 顶点v
     * @return int 出度
     * @author Minuy
     * @date 2021/11/28 10:52
     */
    public int outdegree(String v) {
        if (!isDirected()) {
            throw new RuntimeException("The outdegree only works in directed graph.");
        }
        validateVertex(v);
        return adj.get(v).size();
    }


    /**
     * 倒图， 针对于有向图
     *
     * @return WeightedGraph 倒图
     * @author Minuy
     * @date 2021/11/27 17:15
     */
    public WeightedGraphDynamic reverse() {

        if (!this.isDirected()) {
            throw new RuntimeException("The reverse only works in directed graph.");
        }

        try {
            WeightedGraphDynamic g = (WeightedGraphDynamic) super.clone();
            g.V = this.V;
            g.E = this.E;
            g.adj = new HashMap<>();
            g.isDirected = this.isDirected();

            // 添加顶点
            for (Map.Entry<String, Map<String, Integer>> v : adj.entrySet()) {
                Map<String, Integer> table = new HashMap<>();
                adj.put(v.getKey(), table);
            }

            // 反向添加边
            for (Map.Entry<String, Map<String, Integer>> v : adj.entrySet()) {
                for (Map.Entry<String, Integer> entry : v.getValue().entrySet()) {
                    g.adj.get(entry.getKey()).put(v.getKey(), entry.getValue());
                }
            }

            return g;
        } catch (CloneNotSupportedException e) {
            e.printStackTrace();
        }
        return null;
    }


    /**
     * 深复制
     *
     * @return Graph 返回一个图
     * @author Minuy
     * @date 2021/11/24 22:05
     */
    @Override
    public WeightedGraphDynamic clone() {
        try {
            WeightedGraphDynamic g = (WeightedGraphDynamic) super.clone();
            g.V = this.V;
            g.E = this.E;
            g.adj = new HashMap<>();
            g.isDirected = this.isDirected();
            for (Map.Entry<String, Map<String, Integer>> v : adj.entrySet()) {
                Map<String, Integer> table = new HashMap<>();
                for (Map.Entry<String, Integer> e : v.getValue().entrySet()) {
                    table.put(e.getKey(), e.getValue());
                }
                adj.put(v.getKey(), table);
            }
            return g;
        } catch (CloneNotSupportedException e) {
            e.printStackTrace();
        }
        return null;
    }

    /**
     * 查询图是有向的还是无向的
     *
     * @return boolean 图的方向性
     * @author Minuy
     * @date 2021/11/27 9:08
     */
    public boolean isDirected() {
        return isDirected;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append(String.format("V = %d, E = %d, isDirected = %s\n", V, E, isDirected));
        for (Map.Entry<String, Map<String, Integer>> v : adj.entrySet()) {
            sb.append(String.format("%s : ", v.getKey()));
            int i = 0;
            for (Map.Entry<String, Integer> entry : v.getValue().entrySet()) {
                sb.append(String.format("{%s:%d}", entry.getKey(), entry.getValue()));
                if (i != v.getValue().size() - 1) {
                    sb.append(", ");
                }
                i++;
            }
            sb.append("\n");
        }
        return sb.toString();
    }
}
